Newton's method is an iterative method that has proven to be an effective way to solve for the roots of a polynomial equation. It is particularly attractive as a computational method in a high speed computer when the computer has a hardware floating point multiplier and a hardware floating point adder-subtractor.
In the above case, a hardware implementation of Newton's method can be used to rapidly compute the floating point reciprocal or floating point reciprocal square root of an unknown value C which in turn can be used to compute floating point divide or square root operations.
In general, the Newton's method solves F(x)=0 given that the function F(x) is defined and twice differentiable on the interval (a,b). The algorithm is given as: EQU x.sub.(m+1 =x.sub.m -F(x.sub.m)/F'(x.sub.m)
where:
x.sub.0 =is an initial approximation for F(x)=0, PA1 x.sub.m =is the mth iteration, PA1 x.sub.(m+1) =is the (m+1)st iteration, and PA1 F'(x.sub.m)=is the first derivative of F() evaluated at x.sub.m.
Newton's method for the specific case of determining reciprocal involves solving: EQU F(x)=x.sup.-1 -C
and the Newton iteration is given by: EQU x.sub.(m+1 =x.sub.m {2-cx.sub.m }
for F(x)=0, x.sup.-1 =C and x is equal to the reciprocal of C.
Prior state-of-the-art hardware implementations have revolved around decomposing each Newton iteration into the following successive computations: ##EQU2##
Each step requires only the use of a multiplier or an adder. Hence, each Newton iteration requires three operations.
The improved method forms the Newton iteration in the following two steps versus the three steps as in prior art: ##EQU3##
Newton's method for the specific case of determining reciprocal square roots involves solving: EQU F(x)=x.sup.-2 -C=0
and the Newton iteration is given by: EQU x.sub.(m+1) =0.5x.sub.m {3-cx.sub.m.sup.2 }
for F(x)=0, x.sup.-2 =C and x is the reciprocal square root of C.
Prior state-of-the-art hardware implementations have revolved around decomposing each Newton iteration into the following successive computations: ##EQU4##
Each step requires only the use of a multiplier or an adder. Hence, each Newton iteration requires five operations.
The improved method forms the Newton iteration in the following three steps versus the five steps as in prior art: ##EQU5##